// use std::io::stdin;
// // 不行!!!
// // use crate::Solution;
// // use crate::Solution2;
// // use crate::solution::Solution;
//
//
//
// fn main() {
//     println!("Hello, world!");
//
//     // cargo run 报错 error: linking with `x86_64-w64-mingw32-gcc` failed: exit code: 1
//     // 运行：
//     // rustup target add x86_64-pc-windows-gnu
//     // cargo build --target x86_64-pc-windows-gnu --release
//
//     // 输入
//     let mut str_buf = String::new();
//     stdin().read_line(&mut str_buf).expect("Failed to read line.");
//     println!("str_buf: {}", str_buf);
//     // 检查是否字符串类型
//     // assert_eq!(str_buf.is_ascii(), true);
//
//     // 转化str_buf为数字
//     let num: i32 = str_buf.trim().parse().unwrap();
//     // 输出num
//     println!("num: {}", num);
//     // 检查是否数字类型
//
//
//     // // 还是报错的!
//     // let int_vec: Vec<f32> = str_buf.split(" ")
//     //     .map(|x| x.parse::<f32>().expect("Not an integer!"))
//     //     .collect();
//     //
//     // for i in (0..int_vec.len()).rev() {
//     //     println!("{} ", int_vec[i]);
//     // }
//
//     // 调用Solution中的方法
//     // use of undeclared type `Solution` // 还是错的
//     // let mut solution = Solution::new();
//     // let mut res = solution.count_numbers_with_unique_digits(&num);
//     let res = count_numbers_with_unique_digits(num);
//     // 输出res
//     println!("res: {}", res);
//
//     // 创建整形数组
//     // let int_vec: Vec<i32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
//     // for i in (0..int_vec.len()).rev() {
//     //     println!("{} ", int_vec[i]);
//     // }
//
//     // 输入整形数组
//     let mut int_vec: Vec<i32> = Vec::new();
//     // -i?
//     for _ in 0..2 {
//         let mut str_buf = String::new();
//         stdin().read_line(&mut str_buf).expect("Failed to read line.");
//         let int_buf: i32 = str_buf.trim().parse().unwrap();
//         int_vec.push(int_buf);
//     }
//     for i in (0..int_vec.len()).rev() {
//         println!("{} ", int_vec[i]);
//     }
//
//     // 整体数组转字符串
//     let mut str_buf = String::new();
//     for i in 0..int_vec.len() {
//         str_buf.push_str(&int_vec[i].to_string());
//         str_buf.push_str(" ");
//     }
//     println!("str_buf: {}", str_buf);
//
//
//     // $env:RUST_BACKTRACE=1 ; cargo run -- 语法不正确？！！
//     // 在cmd中执行 set RUST_BACKTRACE=1 -- 还是报错的!!
//     // set RUST_BACKTRACE=full  -- 还是报错的!!
//     // 在powershell中执行 $Env:RUST_BACKTRACE=1
//     // UNIX: RUST_BACKTRACE=1 cargo run
//
//     // 注意：目前 Rust 标准库还没有提供直接从命令行读取数字或格式化数据的方法，我们可以读取一行字符串并使用字符串识别函数处理数据。
//     // std::fs::File 的 open 方法是"只读"打开文件，并且没有配套的 close 方法，因为 Rust 编译器可以在文件不再被使用时自动关闭文件。
//
//     // let r = Circle{r:10.5};
//     // println!("area = {:?}", r.area());
//
//     // let f = Fruit {color:String::from(str_buf), weight:12.5};
//     // f.print_info();
//     // Fruit{color:String::from(str_buf), weight:12.5}.print_info();
//     //Fruit::new(String::from(str_buf), 12.5).print_info();
//     // let r = Circle{r:str_buf};
//     // println!("area = {:?", r.read());
//
//     /*
//     for i in 0..4 {
//         let mut str_buf = String::new();
//         stdin().read_line(&mut str_buf).expect("Failed to read line.");
//         println!("str_buf: {}", str_buf);
//         // 加入数组
//         input_array[i] = str_buf.parse::<i32>().unwrap();
//     }
//     */
//
//     // 输出数组 // {:#?} 占位符
//     // println!("input_array: {:#?}", str_buf);
//
//     // let (mut sx, sy,  tx, ty) = (input_array[0], input_array[1],input_array[2], input_array[3]);
//     // 调用Solution类
//     // let res = Solution::reaching_points(sx, sy,  tx, ty);
//     // println!("res: {}", res);
//
//     // let res2 = Solution2{}.reaching_points(sx, sy,  tx, ty);
//     // println!("res2: {}", res2);
// }
//
//
// /*
// trait Area {
//     fn area(&self) -> f64;
// }
//
// struct Circle {
//     r: f64
// }
//
// impl Area for Circle {
//     fn area(&self) -> f64 {
//         (3.14 * self.r)
//     }
// }
// */
//
//
// // impl Solution {
// //     pub fn count_numbers_with_unique_digits(n: i32) -> i32 {
// //         1 + (1..=n).map(|i| 9 * (11 - i..10).product::<i32>()).sum::<i32>()
// //     }
// //
// //     // 调用方法
// //     // let res = Solution::count_numbers_with_unique_digits(2);
// //     // println!("res: {}", res);
// //
// // }
//
// pub fn count_numbers_with_unique_digits(n: i32) -> i32 {
//     1 + (1..=n).map(|i| 9 * (11 - i..10).product::<i32>()).sum::<i32>()
// }


// use std::io::stdin;
//
// fn main() {
//     println!("Hello, world!");
//
//     // 输入
//     let mut str_buf = String::new();
//     stdin().read_line(&mut str_buf).expect("Failed to read line.");
//     println!("str_buf: {}", str_buf);
//     // 检查是否字符串类型
//     // assert_eq!(str_buf.is_ascii(), true);
//
//     // 转化str_buf为数字
//     let num: i32 = str_buf.trim().parse().unwrap();
//     // 输出num
//     println!("num: {}", num);
//     // 检查是否数字类型：不知道rust有没有检查数据类型的函数？
//
//     let res = count_numbers_with_unique_digits(num);
//     // 输出res
//     println!("res: {}", res);
//
//     // 创建整形数组
//     // let int_vec: Vec<i32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
//     // for i in (0..int_vec.len()).rev() {
//     //     println!("{} ", int_vec[i]);
//     // }
//
//     // 输入整形数组
//     let mut int_vec: Vec<i32> = Vec::new();
//     // 给整形数组输入两个整型数
//     for _ in 0..2 {
//         let mut str_buf = String::new();
//         stdin().read_line(&mut str_buf).expect("Failed to read line.");
//         let int_buf: i32 = str_buf.trim().parse().unwrap();
//         int_vec.push(int_buf);
//     }
//     // 遍历输出整形数组
//     for i in (0..int_vec.len()).rev() {
//         println!("{} ", int_vec[i]);
//     }
//
//     // 整体数组转字符串
//     let mut str_buf = String::new();
//     for i in 0..int_vec.len() {
//         str_buf.push_str(&int_vec[i].to_string());
//         str_buf.push_str(" ");
//     }
//     println!("str_buf: {}", str_buf);
// }

// 引入solution.rs文件
// could not find `solution` in the crate root
// use crate::solution::Solution;

// fn main() {
//     println!("Hello, world!");
//     // 调用 count_numbers_with_unique_digits()方法
//     // not found in this scope
//     // let res = Solution::count_numbers_with_unique_digits(2);
//     // println!("res: {}", res);
// }


// 不用不能写！！
// impl SolutionTwo {
//     // 暂时不知如何调用？？？？
//     pub fn count_numbers_with_unique_digits(n: i32) -> i32 {
//         1 + (1..=n).map(|i| 9 * (11 - i..10).product::<i32>()).sum::<i32>()
//     }
// }


// impl Solution {
//     pub fn reorder_log_files(logs: Vec<String>) -> Vec<String> {
//         let mut logs = logs;
//         logs.sort_by_key(|a| {
//             let splitted = a.split(' ').collect::<Vec<&str>>();
//             let mark = splitted[0];
//             let content = splitted[1..].join(" ");
//             let ch = content.chars().next().unwrap();
//             if ch >= '0' && ch <= '9' {
//                 return (1, String::new(), String::new());
//             }
//             (0, content, String::from(mark))
//         });
//         logs
//     }
// }

// use std::io::stdin;
//
// impl Solution {
//     pub fn find_the_winner(n: i32, k: i32) -> i32 {
//         use std::collections::VecDeque;
//         let mut queue = VecDeque::new();
//         for i in 1..=n {
//             queue.push_back(i);
//         }
//         while queue.len() > 1 {
//             for _ in 1..k {
//                 let first = queue.pop_front().unwrap();
//                 queue.push_back(first);
//             }
//             queue.pop_front();
//         }
//         // 返回值就不用逗号了
//         queue.pop_front().unwrap()
//     }
// }


// fn main() {
//     // 输入整数
//     let mut str_buf = String::new();
//     stdin().read_line(&mut str_buf).expect("Failed to read line.");
//     // 定义变量n
//     let n: i32 = str_buf.trim().parse().unwrap();
//     // 定义变量k
//     let mut str_buf = String::new();
//     stdin().read_line(&mut str_buf).expect("Failed to read line.");
//     let k: i32 = str_buf.trim().parse().unwrap();
//     // 调用find_the_winner()方法
//     let res = Solution::find_the_winner(n, k);
//     println!("res: {}", res);
// }

// use std::cmp::Ordering;
// use std::io;
// use rand::Rng; // gen_range
//
//
// fn main() {
//     println!("猜数游戏!");
//     // supplied 2 arguments expected 1 argument
//     // rand 0.7几的是1,101,现在用的0.8.5版本，它变成1..101了!!
//     let secret_number = rand::thread_rng().gen_range(1..101);
//     // `i32` doesn't implement `Display` (required by {})
//     // println!("神秘数字是：{}", secret_number);
//     println!("神秘数字是：{}", secret_number.expect("secret_number is None"));
//
//     loop {
//         println!("猜测一个数");
//
//         let mut guess = String::new();
//         io::stdin().read_line(&mut guess).expect("Failed to read line");
//         let guess: u32 = match guess.trim().parse() {
//             Ok(num) => num,
//             Err(_) => continue,
//         };
//         println!("你猜的数字是：{}", guess.expect("guess is None"));
//         match guess.cmp(&secret_number) {
//             Ordering::Less => println!("猜小了"),
//             Ordering::Greater => println!("猜大了"),
//             Ordering::Equal => {
//                 println!("猜对了");
//                 break;
//             }
//         }
//     }
// }


// // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
//
// use std::rc::Rc;
// use std::cell::RefCell;
// use std::str::SplitWhitespace;
// struct Codec {}
//
// /**
//   * `&self` means the method takes an immutable reference
//   * If you need a mutable reference, change it to `&mut self` instead
//   *
//  */
//
// impl Codec {
//     fn new() -> Self {
//         Self {}
//     }
//
//     fn serialize(&self, root: Option<Rc<RefCell<TreeNode>>>) -> String {
//         self.pre_order(&root)
//     }
//
//     fn pre_order(&self, root: &Option<Rc<RefCell<TreeNode>>>) -> String {
//         if let Some(node) = root {
//             format!(
//                 "{} {} {}",
//                 node.borrow().val.to_string(),
//                 self.pre_order(&node.borrow().left),
//                 self.pre_order(&node.borrow().right),
//             )
//         } else {
//             ",".to_string()
//         }
//     }
//
//     fn deserialize(&self, data: String) -> Option<Rc<RefCell<TreeNode>>> {
//         if data.len() == 0 {
//             return None;
//         }
//
//         let mut vec = data.split_whitespace();
//
//         self.constructor(&mut vec)
//     }
//
//     fn constructor(&self, iter: &mut SplitWhitespace) -> Option<Rc<RefCell<TreeNode>>> {
//         if let Some(val) = iter.next() {
//             if val != "," {
//                 let node = Rc::new(RefCell::new(TreeNode::new(val.parse::<i32>().unwrap())));
//                 node.borrow_mut().left = self.constructor(iter);
//                 node.borrow_mut().right = self.constructor(iter);
//                 Some(node)
//             } else {
//                 None
//             }
//         } else {
//             None
//         }
//     }
// }
//
// /**
//  * Your Codec object will be instantiated and called as such:
//  * let obj = Codec::new();
//  * let data: String = obj.serialize(strs);
//  * let ans: Option<Rc<RefCell<TreeNode>>> = obj.deserialize(data);
//  */
//
// fn main() {
//     // 1、要编写stringToTreeNode和TreeNodeToString函数，将字符串转换成TreeNode，和TreeNode转换成字符串。
//     // 2、貌似调用impl要用型如#[derive(Debug, PartialEq, Eq)]？？目前还不知如何调用？？
//     let obj = Codec::new();
//     let data: String = obj.serialize(strs);
//     let ans: Option<Rc<RefCell<TreeNode>>> = obj.deserialize(data);
// }


// impl Solution1 {
//     pub fn min_deletion_size(strs: Vec<String>) -> i32 {
//         let mut ans = 0;
//         let rows = strs.len();
//         let cols = strs[0].len();
//
//         for j in 0..cols {
//             for i in 0..(rows - 1) {
//                 if strs[i].get(j..=j).unwrap() > strs[i+1].get(j..=j).unwrap() {
//                     ans += 1;
//                     break;
//                 }
//             }
//         }
//
//         ans
//     }
// }


// impl Solution {
//     pub fn min_deletion_size(strs: Vec<String>) -> i32 {
//         let mut ret = 0;
//         let strs_arr = strs.iter().map(|s| s.chars().collect::<Vec<char>>()).collect::<Vec<_>>();
//         for i in 0..strs[0].len() {
//             for j in 1..strs.len() {
//                 if strs_arr[j - 1][i] > strs_arr[j][i] {
//                     ret += 1;
//                     break;
//                 }
//             }
//         }
//         ret
//     }
// }
//
// fn main() {
//     let strs = vec!["cba".to_string(), "daf".to_string(), "ghi".to_string()];
//     println!("{:?}", Solution::min_deletion_size(strs));
// }


// impl Solution {
//     pub fn valid_ip_address(query_ip: String) -> String {
//         use std::str::FromStr;
//         fn is_ipv4(arr: Vec<&str>) -> bool {
//             if arr.len() != 4 { return false; }
//             for ip in arr {
//                 if ip.len() < 1 || ip.len() > 3 { return false; }
//                 let ip_num = ip.parse::<i32>();
//                 if ip_num.is_err() || ip_num.as_ref().unwrap() > &255 || ip_num.as_ref().unwrap().to_string().len() != ip.len() { return false; }
//             }
//             true
//         }
//         fn is_ipv6(arr: Vec<&str>) -> bool {
//             if arr.len() != 8 { return false; }
//             for ip in arr {
//                 if ip.len() < 1 || ip.len() > 4 { return false; }
//                 for ch in ip.chars() {
//                     if !char::is_ascii_digit(&ch) && !(ch >= 'a' && ch <= 'f' || ch >= 'A' && ch <= 'F') { return false; }
//                 }
//             }
//             true
//         }
//
//         if query_ip.contains(".") {
//             return if !is_ipv4(query_ip.split(".").collect::<Vec<_>>()) { "Neither".to_string() } else { "IPv4".to_string() };
//         }
//         return if !is_ipv6(query_ip.split(":").collect::<Vec<_>>()) { "Neither".to_string() } else { "IPv6".to_string() };
//     }
// }
//
//
// // 方法2：函数式+std::net|ipaddress+微调IPv6
// impl Solution2 {
//     pub fn valid_ip_address(query_ip: String) -> String {
//         use std::net::{Ipv4Addr, Ipv6Addr};
//         query_ip
//             .parse::<Ipv4Addr>()
//             .map(|_| String::from("IPv4"))
//             .or(query_ip
//                 .split(":")
//                 .map(|x| if x.is_empty() { "g" } else { x })
//                 .collect::<Vec<_>>()
//                 .join(":")
//                 .parse::<Ipv6Addr>()
//                 .map(|_| String::from("IPv6")))
//             .unwrap_or_else(|_| String::from("Neither"))
//     }
// }

// use std::collections::HashSet;
//
//
// impl Solution1 {
//     pub fn num_unique_emails(emails: Vec<String>) -> i32 {
//         let mut set = HashSet::new();
//         for email in &emails {
//             let mut ignore = false;
//             let mut append = false;
//             let mut sb = String::new();
//             for c in email.chars() {
//                 if append {
//                     sb.push(c);
//                 } else {
//                     if c == '@' {
//                         sb.push(c);
//                         append = true;
//                         continue;
//                     }
//                     if ignore || c == '.' {
//                         continue;
//                     }
//                     if c == '+' {
//                         ignore = true;
//                         continue;
//                     }
//                     sb.push(c);
//                 }
//             }
//             set.insert(sb);
//         }
//         set.len() as i32
//     }
// }
//
//
// impl Solution2 {
//     pub fn num_unique_emails(emails: Vec<String>) -> i32 {
//         let mut set = HashSet::new();
//         for email in &emails {
//             let mut ignore = false;
//             let mut append = false;
//             let mut sb = String::new();
//             for c in email.chars() {
//                 if append {
//                     sb.push(c);
//                 } else {
//                     if  c == '@' {
//                         sb.push(c);
//                         append = true;
//                         continue;
//                     }
//                     if ignore || c == '.' {
//                         continue;
//                     }
//                     if c == '+' {
//                         ignore = true;
//                         continue;
//                     }
//                     sb.push(c);
//                 }
//             }
//             set.insert(sb);
//         }
//         set.len() as i32
//     }
// }
//
//
// impl Solution {
//     pub fn num_unique_emails(emails: Vec<String>) -> i32 {
//         let mut tab = std::collections::HashSet::with_capacity(emails.len());
//         for e in emails.into_iter() {
//             let e: Vec<_> = e.split("@").collect();
//             let local: Vec<_> = e[0].split('+').collect();
//             tab.insert(format!("{}@{}", local[0].replace(".", ""), e[1]));
//         }
//         tab.len() as i32
//     }
// }





//  #[derive(PartialEq, Eq, Debug, Clone)]
//  pub struct ListNode {
//      pub val: i32,
//      pub next: Option<Box<ListNode>>
//  }
//  impl ListNode {
//      #[inline]
//      fn new(val: i32) -> Self {
//          ListNode {
//              val: val,
//              next: None,
//          }
//      }
//  }
//
//
// struct Solution{
//
// }
//
// impl Solution {
//     fn new() -> Self {
//         Solution{}
//     }
//
//     /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//         * @param head ListNode类
//         * @return ListNode类
//      */
//     pub fn ReverseList(&self, head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
//         // write code here
//         let mut res=None;
//         let mut cur=head;
//         while let Some(mut x)=cur{
//             cur=x.next;
//             // x.next 报错？？
//             x.next=res;
//             res=Some(x);
//         }
//         res
//
//     }
// }
//
//
// /**
//  *  #[derive(PartialEq, Eq, Debug, Clone)]
//  *  pub struct ListNode {
//  *      pub val: i32,
//  *      pub next: Option<Box<ListNode>>
//  *  }
//  *
//  *  impl ListNode {
//  *      #[inline]
//  *      fn new(val: i32) -> Self {
//  *          ListNode {
//  *              val: val,
//  *              next: None,
//  *          }
//  *      }
//  *  }
//  */
//
// impl Solution2 {
//     fn new() -> Self {
//         Solution{}
//     }
//
//     /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//         * @param head ListNode类
//         * @return ListNode类
//      */
//     pub fn ReverseList(&self, head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
//         let mut prev = None;
//         let mut node = head;
//         loop {
//             match &mut node {
//                 Some(n) => {
//                     let next = n.next.take();
//                     n.next = prev;
//                     prev = node;
//                     node = next;
//                 }
//                 None => break,
//             }
//         }
//         prev
//     }
// }


// // Rng 报错
// use rand::{thread_rng, Rng};
//
// struct Solution {
//     radius: f64,
//     x_center: f64,
//     y_center: f64,
// }
//
// /**
//  * `&self` means the method takes an immutable reference.
//  * If you need a mutable reference, change it to `&mut self` instead.
//  */
// impl Solution {
//     fn new(radius: f64, x_center: f64, y_center: f64) -> Self {
//         Self {
//             radius,
//             x_center,
//             y_center,
//         }
//     }
//
//     fn rand_point(&self) -> Vec<f64> {
//         let mut rng = thread_rng();
//         let delta_x = rng.gen_range(-self.radius, self.radius);
//         let delta_y = rng.gen_range(-self.radius, self.radius);
//
//         if delta_x.powi(2) + delta_y.powi(2) <= self.radius.powi(2) {
//             vec![self.x_center + delta_x, self.y_center + delta_y]
//         } else {
//             self.rand_point()
//         }
//     }
// }
//
// /**
//  * Your Solution object will be instantiated and called as such:
//  * let obj = Solution::new(radius, x_center, y_center);
//  * let ret_1: Vec<f64> = obj.rand_point();
//  */



// use std::arch::x86_64:: _rdrand64_step;//478. 在圆内随机生成点
//
// //478. 在圆内随机生成点
// struct Solution {
//     diameter: f64,
//     left_down_point: (f64, f64),
//     center: (f64, f64),
// }
//
// impl Solution {
//     fn new(radius: f64, x_center: f64, y_center: f64) -> Self {
//         //平台自带的随机方式为随机一个u64,将随机到的u64转变为一个0-1之间的f64
//         Self {
//             diameter: 2.0 * radius,
//             left_down_point: (x_center - radius, y_center - radius),
//             center: (x_center, y_center),
//         }
//     }
//
//     fn rand_f64(&self) -> f64 {
//         let mut num = 0;
//         unsafe {
//             _rdrand64_step(&mut num)
//         };
//         (num as f64 / u64::MAX as f64) * self.diameter
//     }
//
//     fn is_out_circle(&self, (x, y): (f64, f64)) -> bool {
//         (x - self.center.0).powi(2) + (y - self.center.1).powi(2)
//             > self.diameter * self.diameter / 4.0
//     }
//
//
//     fn rand_point(&self) -> Vec<f64> {
//         let x = self.rand_f64() + self.left_down_point.0;
//         let y = self.rand_f64() + self.left_down_point.1;
//         if self.is_out_circle((x,y)){
//             return self.rand_point();
//         }
//         vec![x,y]
//     }
// }



// use rand::distributions::{Distribution, Uniform};
//
// struct Solution {
//     x: f64,
//     y: f64,
//     r: f64,
// }
//
// /**
//  * `&self` means the method takes an immutable reference.
//  * If you need a mutable reference, change it to `&mut self` instead.
//  */
// impl Solution {
//     fn new(radius: f64, x_center: f64, y_center: f64) -> Self {
//         Solution {
//             x: x_center,
//             y: y_center,
//             r: radius,
//         }
//     }
//
//     fn rand_point(&self) -> Vec<f64> {
//         let mut rng = rand::thread_rng();
//         let die = Uniform::from(-self.r..=self.r);
//         loop {
//             let (x, y): (f64, f64) = (die.sample(&mut rng), die.sample(&mut rng));
//             if x * x + y * y <= self.r * self.r {
//                 return vec![x + self.x, y + self.y];
//             }
//         }
//     }
// }
//
//
// /**
//  * Your Solution object will be instantiated and called as such:
//  * let obj = Solution::new(radius, x_center, y_center);
//  * let ret_1: Vec<f64> = obj.rand_point();
//  */



// // 放头部就报错，为啥？？
// // use rand::{thread_rng,Rng};
// struct Solution {
//     radius:f64,
//     x_center:f64,
//     y_center:f64,
//     r_2:f64,
// }
//
// impl Solution {
//
//     fn new(radius: f64, x_center: f64, y_center: f64) -> Self {
//         Solution {radius, x_center, y_center,r_2:radius * radius}
//     }
//
//     fn rand_point(&self) -> Vec<f64> {
//         // Rng 局部用就不报错？
//         use rand::{thread_rng,Rng};
//         let mut rng = thread_rng();
//         let (x,y) = loop {
//             let (x,y) = (rng.gen_range(-self.radius, self.radius),rng.gen_range(-self.radius, self.radius));
//             if x * x + y * y <= self.r_2 {
//                 break (x,y);
//             }
//         };
//         vec![x + self.x_center,y+ self.y_center]
//     }
// }



// // 常规DFS + 剪枝100%
// impl Solution {
//     pub fn makesquare(mut matchsticks: Vec<i32>) -> bool {
//         let (mut m, n) = (matchsticks.len() as i32, matchsticks.iter().sum::<i32>());
//         if n % 4 != 0 { return false; }
//
//         fn dfs(m: i32, n: i32, side: &mut Vec<i32>, matchsticks: &Vec<i32>) -> bool {
//             if m == -1 { return true; }
//             for i in 0..4 {
//                 if side[i] == n || side[i] + matchsticks[m as usize] > n || (i > 0 && side[i] == side[i - 1]) { continue; }
//                 side[i] += matchsticks[m as usize];
//                 if dfs(m - 1, n, side, matchsticks) { return true; }
//                 side[i] -= matchsticks[m as usize];
//             }
//             false
//         }
//         matchsticks.sort();
//         dfs(m - 1, n / 4, &mut vec![0; 4], &matchsticks)
//     }
// }
//
// // 回溯
// impl Solution2 {
//     pub fn makesquare(mut matchsticks: Vec<i32>) -> bool {
//         let sum = matchsticks.iter().sum::<i32>();
//         let l = sum >> 2;
//         if sum % 4 != 0 || matchsticks.iter().any(|x| x > &l) {
//             return false;
//         }
//         matchsticks.sort_by(|a, b| b.cmp(a));
//
//         let len = matchsticks.len();
//         // 用来存储当前火柴放在哪条边上，也是当前火柴所放位置的起始范围。从0开始放。
//         let mut map = vec![0; len];
//         // 当前放的火柴索引
//         let mut i = 0;
//         // 四条边的状态，放入一根火柴或者回溯的时候就更新长度，
//         let mut arr = [0, 0, 0, 0];
//         let mut res = true;
//
//         loop {
//             // 标识当前火柴放到边上没有
//             let mut flag = false;
//             // 因为是依次放的，map[i] >= 4的时候就是没有合适的位置可以放了。准备回溯
//             if map[i] < 4 {
//                 for j in map[i]..4 {
//                     // 当前边可以放下火柴，更新map，更新边
//                     if arr[j] + matchsticks[i] <= l {
//                         map[i] = j;
//                         arr[j] += matchsticks[i];
//                         flag = true;
//                         break;
//                     }
//                 }
//             }
//
//             // 如果最后一根火柴放到边上了，那就表示完成了正方形
//             if flag && i == len - 1 {
//                 break;
//             }
//             // 回溯的边界，第0根火柴任何地方都放不下了，return false
//             if !flag && i == 0 {
//                 res = false;
//                 break;
//             }
//             // 回溯，当前火柴的起始置为0，上一根火柴放的边长度更新，上一根火柴的起始位置 += 1;
//             if !flag {
//                 map[i] = 0;
//                 i -= 1;
//                 let j = map[i];
//                 arr[j] -= matchsticks[i];
//                 map[i] += 1;
//             } else {
//                 // 正常放下了，就开始放下一根火柴
//                 i += 1;
//             }
//         }
//         res
//     }
// }
//
//
// // 也不知道怎么调用的？？


// use std::f64;
//
// pub struct Solution{}
//
// impl Solution{
//     pub fn reach_number(target:i32)->i32 {
//         let target=target.abs();
//         let mut n=f64::sqrt(2.0*target as f64) as i32;
//         let mut sum=n*(n+1)/2;
//         while sum<target {
//             n+=1; sum+=n;
//         }
//         while (sum-target)%2==1 {
//             n+=1; sum+=n;
//         }
//         n
//     }
// }
//
// #[cfg(test)]
// mod tests {
//     use super::*;
//
//     #[test]
//     fn test_1() {
//         // 输出 1!!
//         println!("{}", Solution::reach_number(1));
//         assert_eq!(Solution::reach_number(1),1);
//         assert_eq!(Solution::reach_number(2),3);
//         assert_eq!(Solution::reach_number(3),2);
//         assert_eq!(Solution::reach_number(7),5);
//         assert_eq!(Solution::reach_number(8),4);
//         assert_eq!(Solution::reach_number(12),7);
//     }
//
//     #[test] fn test_2() {
//         assert_eq!(Solution::reach_number(-1),1);
//         assert_eq!(Solution::reach_number(-2),3);
//         assert_eq!(Solution::reach_number(-3),2);
//         assert_eq!(Solution::reach_number(-7),5);
//         assert_eq!(Solution::reach_number(-8),4);
//         assert_eq!(Solution::reach_number(-12),7);
//     }
// }


// pub struct Solution {}
//
// // 1200. 最小绝对差
// impl Solution {
//     pub fn minimum_abs_difference(mut arr: Vec<i32>) -> Vec<Vec<i32>> {
//         let len = arr.len();
//         let mut ret = Vec::new();
//         let mut dv = vec![0; len-1];
//         arr.sort();
//         for i in 1..len {
//             dv[i-1] = arr[i] - arr[i-1];
//         }
//         let min = dv.iter().min().unwrap();
//         let mut i = 0;
//         for d in &dv {
//             if d == min {
//                 ret.push(vec![arr[i], arr[i+1]]);
//             }
//             i += 1;
//         }
//         ret
//     }
// }
//
//
// #[cfg(test)]
// mod test {
//     use super::*;
//
//     #[test]
//     fn test_1() {
//         // let mut arr: Vec<i32> 把Vec<i32>去掉！！
//         // !vec([4,2,1,3]) 去掉()号！！感叹号在后面!!
//         // 加mut warning: variable does not need to be mutable
//         let arr = vec![4,2,1,3];
//         // 字符串等用{}，向量vec用{:?}
//         println!("{:?}", Solution::minimum_abs_difference(arr));
//         // 这个arr报错的，为啥？？
//         // assert_eq!(Solution::minimum_abs_difference(arr), [[1,2],[2,3],[3,4]]);
//     }
// }
//
//
// // 不能少，少报错的!!!
// fn main() {
//
// }


// // use of undeclared type `Solution`
// pub struct Solution {}
//
// impl Solution {
//     pub fn min_cost_to_move_chips(position: Vec<i32>) -> i32 {
//         // rust 不可以， java可以
//         // let odd = 0, event = 0;
//         let mut odd = 0;
//         let mut event = 0;
//         for num in position {
//             if num & 1 == 0 {
//                 // rust 不可以
//                 // event++;
//                 event += 1;
//             } else {
//                 odd += 1;
//             }
//         }
//         // 加return 也不报错的
//         // return 0
//         // 返回值不加逗号; // 可以java用Math.min()，c++用min不同!
//         // return odd.min(event)
//         odd.min(event)
//     }
//
//     //
//     pub fn min_cost_to_move_chips_2(position: Vec<i32>) -> i32 {
//         // iter()统计偶数
//         let odd = position.iter().filter(|&x| x & 1 == 1).count();
//         // 要加 as i32 要不报错
//         odd.min(position.len() - odd) as i32
//     }
// }
//
//
// fn main() {
//
// }
//
// #[cfg(test)]
// mod tests {
//     use super::*;
//
//     #[test]
//     fn test_1() {
//         // expected struct `Vec`, found array `[{integer}; 3]`
//         // let p = [1,2,3];
//         // ^ expected `i32`, found array `[{integer}; 3]`
//         // let mut p = vec!([1,2,3]);
//         // vec!没有括号()!!!
//         // warning:  help: remove this `mut`
//         // let mut p = vec![1,2,3];
//         let p = vec![1,2,3];
//         //  ^ expected `i32`, found array `[{integer}; 3]`
//         // let res = Solution::min_cost_to_move_chips(p);
//         // warning:  help: remove this `mut`
//         // let mut res = Solution::min_cost_to_move_chips(p);
//         let res = Solution::min_cost_to_move_chips(p);
//         println!("{}", res);
//         assert_eq!(res, 1);
//     }
// }

// pub struct Solution {}
//
// impl Solution {
//     pub fn odd_cells(m: i32, n: i32, indices: Vec<Vec<i32>>) -> i32 {
//         let mut row = 0u64;
//         let mut col = 0u64;
//
//         for e in &indices {
//             let ri = e[0] as u64;
//             let ci = e[1] as u64;
//             row ^= 1u64 << ri;
//             col ^= 1u64 << ci;
//         }
//
//         let cx = row.count_ones() as i32;
//         let cy = col.count_ones() as i32;
//         cx * (n - cy) + cy * (m - cx)
//     }
// }
//
// fn main() {}
//
//
// #[cfg(test)]
// mod tests {
//     use super::*;
//
//     #[test]
//     fn test_1() {
//         let m = 2;
//         let n = 3;
//         let mut odd_cells = vec![vec![0,1],vec![1,1]];
//         println!("{}", Solution::odd_cells(m, n, odd_cells));
//
//         // m,n整数可以不用mut，但向量vec必须再次赋值再用!
//         odd_cells = vec![vec![0,1],vec![1,1]];
//         assert_eq!(Solution::odd_cells(m, n, odd_cells), 6);
//     }
// }
//
// /*
// 2
// 3
// [[0,1],[1,1]]
// */


// use std::rc::Rc;
// use std::cell::RefCell;
// use std::mem::swap;
//
// // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//   pub val: i32,
//   pub left: Option<Rc<RefCell<TreeNode>>>,
//   pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//   #[inline]
//   pub fn new(val: i32) -> Self {
//     TreeNode {
//       val,
//       left: None,
//       right: None
//     }
//   }
// }
//
// impl Solution {
//     pub fn max_level_sum(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
//         use std::collections::VecDeque;
//         let (mut ret, mut sum, mut level, mut maximum) = (0, 0, 1, i32::MIN);
//         let (mut queue, mut next) = (VecDeque::new(), VecDeque::new());
//
//         queue.push_back(root.unwrap());
//         while let Some(mut curr) = queue.pop_front() {
//             sum += curr.as_ref().borrow().val;
//             if curr.as_ref().borrow().left.is_some() { next.push_back(curr.as_ref().borrow().left.as_ref().unwrap().clone()); }
//             if curr.as_ref().borrow().right.is_some() { next.push_back(curr.as_ref().borrow().right.as_ref().unwrap().clone()); }
//             if queue.len() == 0 {
//                 swap(&mut queue, &mut next);
//                 if sum > maximum {
//                     maximum = sum;
//                     ret = level;
//                 }
//                 level += 1;
//                 sum = 0;
//             }
//         }
//         ret
//     }
// }
//
// fn main() {}
//
//
// #[cfg(test)]
// mod tests {
//     use super::*;
//
//     #[test]
//     fn test_1() {
//         root = vec![1,7,0,7,-8,None,None];
//         // 数组或字符串转TreeNode二叉树？？
//     }
// }


// impl Solution1 {
//     pub fn string_matching(words: Vec<String>) -> Vec<String> {
//         let mut ret = Vec![];
//         for i in 0..words.len() {
//             let w = &words[i];
//             for j in 0..words.len() {
//                 if i != j {
//                     continue;
//                 }
//                 let w2 = &words[j];
//                 if w2.contains(w1.as_str()) {
//                     ret.push(w1.clone());
//                     break;
//                 }
//             }
//         }
//         ret
//     }
// }


// pub struct Solution {}
//
// impl Solution {
//     pub fn string_matching(words: Vec<String>) -> Vec<String> {
//         let mut ret = Vec::new();
//
//         for i in 0..words.len() {
//             for j in 0..words.len() {
//                 if j != i && words[j].contains(&words[i]) {
//                     ret.push(words[i].clone());
//                     break;
//                 }
//             }
//         }
//
//         ret
//     }
// }
//
// fn main() {}
//
//
// #[cfg(test)]
// mod tests {
//     use super::*;
//
//     #[test]
//     fn test_1() {
//         // failed to resolve: use of undeclared type `Solution`
//         // let  mut words = vec!["mass","as","hero","superhero"];
//         let mut words = vec!["mass","as","hero","superhero"];
//         // 报错: 怎么Vec<str>转Vec<string>??
//         println!("{:?}", Solution::string_matching(words.to_string());
//         let mut words = vec!["mass","as","hero","superhero"];
//         assert_eq!(Solution::string_matching(words.to_string()), ["as","hero"].to_string());
//     }
// }





// use std::rc::Rc;
// use std::cell::RefCell;
//
//
// // Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//     pub val: i32,
//     pub left: Option<Rc<RefCell<TreeNode>>>,
//     pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//     #[inline]
//     pub fn new(val: i32) -> Self {
//         TreeNode {
//             val,
//             left: None,
//             right: None
//         }
//     }
// }
//
// pub struct Solution {}
//
// // 方法一：深度优先搜索
// impl Solution {
//     pub fn add_one_row(
//         root: Option<Rc<RefCell<TreeNode>>>,
//         val: i32,
//         depth: i32,
//     ) -> Option<Rc<RefCell<TreeNode>>> {
//         fn dfs(root: &Option<Rc<RefCell<TreeNode>>>, cur_depth: i32, max_depth: i32, val: i32) {
//             if root.is_none() {
//                 return;
//             }
//             if cur_depth + 1 == max_depth {
//                 let mut cur_root = root.as_ref().unwrap().borrow_mut();
//                 let left = cur_root.left.take();
//                 let right = cur_root.right.take();
//                 cur_root.left = Some(Rc::new(RefCell::new(TreeNode {
//                     val,
//                     left,
//                     right: None,
//                 })));
//                 cur_root.right = Some(Rc::new(RefCell::new(TreeNode {
//                     val,
//                     left: None,
//                     right,
//                 })));
//                 return;
//             }
//             let t = root.as_ref().unwrap().borrow_mut();
//             dfs(&t.left, cur_depth + 1, max_depth, val);
//             dfs(&t.right, cur_depth + 1, max_depth, val);
//         }
//         if depth == 1 {
//             return Some(Rc::new(RefCell::new(TreeNode {
//                 val,
//                 left: root,
//                 right: None,
//             })));
//         }
//         dfs(&root, 1, depth, val);
//         root
//     }
// }
//
//
// fn main() {}
//
// #[cfg(test)]
// mod tests {
//     use super::*;
//
//     #[test]
//     fn test_1() {
//         // 咋调？？
//     }
// }


// // use std::borrow::Borrow;
// use std::rc::Rc;
// use std::cell::RefCell;
// use std::cmp::max;
// // use std::collections::{HashMap, VecDeque}; HashMap 没使用，报错
// use std::collections::{VecDeque};
//
// // pub struct Solution {}
//
// // Definition for a binary tree node.
// // #[derive(Debug, PartialEq, Eq)] 是rust的一种注解，表示默认实现的trait。
// // 这里表明这个结构体可以打印（Debug）到控制台以及可以比较大小（PartialEq, Eq）。
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
//     pub val: i32,
//     pub left: Option<Rc<RefCell<TreeNode>>>,
//     pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
//     #[inline]
//     pub fn new(val: i32) -> Self {
//         TreeNode {
//             val,
//             left: None,
//             right: None
//         }
//     }
//
//     // 获取二叉树高度
//     pub fn get_height(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
//         fn dfs(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
//             match root {
//                 None => 0,
//                 Some(node) => {
//                     // cannot infer type for type parameter `Borrowed` declared on the trait `Borrow`??
//                     // let node = node.borrow();
//                     let node = node.borrow();
//                     // 返回值，直接没有return标识
//                     1 + max(dfs(&node.left), dfs(&node.right))
//                 }
//             }
//         }
//         dfs(&root)
//     }
//
//     // 通过数组反序列化生成一棵树(一维向量/数组转二叉树)
//     pub fn create(nums: Vec<Option<i32>>) -> Option<Rc<RefCell<Self>>> {
//         if nums.is_empty() {
//             return None;
//         }
//         let size = nums.len();
//         let mut index = 0;
//         let root = Some(Rc::new(RefCell::new(Self::new(nums[0].unwrap()))));
//         let mut queue = VecDeque::new();
//         queue.push_back(root.clone());
//         while !queue.is_empty() {
//             let q_size = queue.len();
//             for _i in 0..q_size {
//                 if let Some(x) = queue.pop_front().flatten() {
//                     let mut node = x.borrow();
//                     let lseq = 2 * index + 1;
//                     let rseq = 2 * index + 2;
//                     if lseq < size && nums[lseq].is_some() {
//                         node.left = Some(Rc::new(RefCell::new(Self::new(nums[lseq].unwrap()))));
//                         queue.push_back(node.left.clone());
//                     }
//
//                     if rseq < size && nums[rseq].is_some() {
//                         node.right = Some(Rc::new(RefCell::new(Self::new(nums[rseq].unwrap()))));
//                         queue.push_back(node.right.clone());
//                     }
//                 }
//                 index += 1;
//             }
//         }
//         root
//     }
//
//     // 将一棵树序列化成一个数组(二叉树转一维向量/数组)
//     pub fn literal(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Option<i32>> {
//         if root.is_none() {
//             return vec![];
//         }
//         let mut ans = vec![];
//         let mut queue = VecDeque::new();
//         queue.push_back(root);
//         while !queue.is_empty() {
//             let qsize = queue.len();
//             for _ in 0..qsize {
//                 match queue.pop_front().flatten() {
//                     Some(x) => {
//                         ans.push(Some(x.borrow().val));
//                         queue.push_back(x.borrow().left.clone());
//                         queue.push_back(x.borrow().right.clone());
//                     }
//                     None => ans.push(None),
//                 }
//             }
//         }
//         let size = ans.len();
//         for i in (0..size).rev() {
//             if ans[i].is_none() {
//                 ans.pop();
//             } else {
//                 break;
//             }
//         }
//         ans
//     }
//
//     // leetcode 655. 输出二叉树(树的拓扑树形进行打印)
//     pub fn print_tree(root: Option<Rc<RefCell<TreeNode>>>) -> String {
//         // 二叉树高度
//         let height = TreeNode::get_height(&root);
//         // 满二叉树的宽度
//         let width = (1 << height) - 1;
//         let mut ans = vec![vec![" ".to_string(); width as usize]; height as usize];
//
//         // dfs 搜索
//         fn dfs(ans: &mut Vec<Vec<String>>, node: &Option<Rc<RefCell<TreeNode>>>, deep: usize, lo: usize, hi: usize) {
//             if let Some(x) = node {
//                 let node = x.borrow();
//                 let mid = lo + (hi - lo) / 2;
//                 ans[deep][mid] = x.borrow().val.to_string();
//                 dfs(ans, &node.left, deep + 1, lo, mid);
//                 dfs(ans, &node.right, deep + 1, mid + 1, hi);
//             }
//         }
//
//         dfs(&mut ans, &root, 0usize, 0usize, width as usize);
//         // 将所有字符连起来
//         ans.iter().map(|x| x.concat()).collect::<Vec<_>>().join("\n")
//     }
//
//     // 自己写的：二叉树数组转字符串
//     pub fn tree_node_array_to_string(ans: Vec<Option<Rc<RefCell<TreeNode>>>>) -> Vec<String> {
//         let mut out = Vec::new();
//         for i in ans.iter() {
//             // println!(i);
//             out.push(TreeNode::print_tree(i.clone()))
//         }
//         out
//     }
//
// }
//
// // // 652. 寻找重复的子树
// // impl Solution {
// //     pub fn find_duplicate_subtrees(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
// //         let mut ans = vec![];
// //         let mut cnt = HashMap::new();
// //
// //         Self::dfs(&mut ans, &mut cnt, root);
// //
// //         // 返回的是元素未二叉树的一维数组
// //         ans
// //     }
// //
// //     fn dfs(ans: &mut Vec<Option<Rc<RefCell<TreeNode>>>>, cnt: &mut HashMap<String, i32>, root: Option<Rc<RefCell<TreeNode>>>) -> String {
// //         if let Some(r) = root {
// //             let left = Self::dfs(ans, cnt, r.borrow_mut().left.clone());
// //             let right = Self::dfs(ans, cnt, r.borrow_mut().right.clone());
// //             let key = format!("{} {} {}", r.borrow_mut().val, left, right);
// //
// //             *cnt.entry(key.clone()).or_insert(0) += 1;
// //
// //             if let Some(&v) = cnt.get(&key) {
// //                 if v == 2 {
// //                     ans.push(Some(r));
// //                 }
// //             }
// //
// //             key
// //         } else {
// //             ",".to_string()
// //         }
// //     }
// // }
//
//
// #[cfg(test)]
// mod tests {
//     use super::*;
//     use std::option::Option::Some;
//
//     #[test]
//     fn test_1() {
//         // rust 这种场景怎么输入？？
//         // let mut arr = vec![1,2,3,4,None,2,4,None,None,4]; 报错
//         // let mut arr: [Option<Vec<i32>>; 10] = [[1,2,3,4,None,2,4,None,None,4]; 10]; 报错
//         // Vec<Option<i32>>
//         // let mut arr = Option(vec![2,1,1]); 报错
//
//         // expected integer, found enum `Option` 报错
//         // let nums = vec![Some(1), Some(2), Some(3), Some(4), None, Some(None), Some(None), Some(4)];
//         let nums = vec![Some(2), Some(1), Some(1)];
//
//         let root = TreeNode::create(nums);
//         println!("{}", TreeNode::print_tree(root));
//
//         // let mut root = TreeNode::create(arr);
//         // 调用函数：652. 寻找重复的子树
//         // let ans = Solution::find_duplicate_subtrees(root); // 报错？
//         // println!("{:?}", ans);
//         // println!("{:?}", TreeNode::tree_node_array_to_string(ans));
//
//         // assert_eq!(vec![0, 1], Solution::find_duplicate_subtrees(vec![2, 7, 11, 15], 9));
//         // assert_eq!(vec![1, 2], Solution::find_duplicate_subtrees(vec![3, 2, 4], 6));
//     }
// }